from typing import NamedTuple, List

Section = NamedTuple('Section', [('length', int), ('height', int)])


def min_cost(heights):
    def get_mid_height(beg, end):
        sorted_heights =  sorted(heights[beg: end])
        mid = (len(sorted_heights) - 1) // 2
        return sorted_heights[mid]

    stack: List[Section] = []
    for i, h in enumerate(heights):
        # suppose [j, i+1) being target_h
        j, target_h = i, h
        while stack and target_h < stack[-1].height:
            section = stack.pop()
            j -= section.length
            target_h = get_mid_height(j, i + 1)
        stack.append(Section(i+1-j, target_h))

    target_heights = []
    for section in stack:
        for i in range(section.length):
            target_heights.append(section.height)

    cost = 0
    for origin_height, target_height in zip(heights, target_heights):
        cost += abs(origin_height - target_height)
    return cost


if __name__ == "__main__":
    num = int(input().strip())
    if num == 0:
        heights_str = input()
        heights = []
    else:
        heights = [int(x) for x in input().strip().split()]

    results = min_cost(heights)
    print(results)
